package com.atbeijing.D03;

import java.util.HashMap;

/**
 * 斐波那契数列
 */
public class Example10 {
    public static void main(String[] args) {
        long t1 = System.currentTimeMillis();
//        System.out.println(Example10.fibonacci(30L));
        System.out.println(Example10.improvedFibonacci(30));
        long t2 = System.currentTimeMillis();
        System.out.println(t2-t1);
    }

    // fib(100) = fib(99) + fib(98) = 2 * fib(98) + fib(97)
    // fib(4) = fib(3) + fib(2) = fib(2) + fib(1) + fib(2) 有重复计算
    public static long fibonacci(Long n){
        if (n==1){
            return 1L;
        }
        if (n==2){
            return 2L;
        }
        return fibonacci(n-1)+fibonacci(n-2);
    }

    //改善1
    public static Long improvedFibonacci(int n) {
        if (n == 1) {
            return 1L;
        }
        if (n == 2) {
            return 2L;
        }
        Long[] arr = new Long[n + 1];
        arr[0] = 0L;
        arr[1] = 1L;
        arr[2] = 2L;
        //将数据提前缓存进数组,避免了重复计算
        for (int i = 3; i <n+1; i++) {
            arr[i]=arr[i-1]+arr[i-2];
        }
        return arr[n];
    }

    //改善2
    public static HashMap<Integer, Long> cache = new HashMap<>();
    public static Long cachedFibonacci(int n) {
        if (!cache.containsKey(n)) {
            //将数据缓存到哈希表
            cache.put(n, fibHelp(n));
        }
        return cache.get(n);
    }
    public static Long fibHelp(int n) {
        if (n == 1 || n == 2) {
            return (long) n;
        }
        return cachedFibonacci(n - 1) + cachedFibonacci(n - 2);
    }


}
